home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d7 / gt1600_1.arc / MEGALINK.DOC < prev    next >
Text File  |  1990-12-15  |  20KB  |  424 lines

  1.  
  2.                                    MEGAlink
  3.                            A File Transfer Protocol
  4.  
  5.                                 Specifications
  6.  
  7.                                By: Paul Meiners
  8.  
  9.                              P&M Software Company
  10.                              3104 E. Camelback Rd.
  11.                              #503
  12.                              Phoenix, AZ  85016
  13.  
  14.                                 April 18, 1987
  15.  
  16.                                Revision history:
  17.                                -----------------
  18.                     August 9, 1987 ... Forsberg's CRC Variation
  19.  
  20.  
  21. Acknowledgements
  22. ----------------
  23. I would like to acknowledge the work of those who have done this before me.
  24. First, Chuck Forsberg, for his never ending quest for speed and reliability.
  25. Second, Ward Christensen, whose ideas are the genesis of this whole branch
  26. of file transfer technology.  Third, Peter Boswell, for showing me the way
  27. to a network friendly protocol.  Last, Tom Jennings, for the work he did
  28. on Fido and the Telink protocol, which introduced the "link" style header
  29. record, now in use by all "link" type protocols.
  30.  
  31. For those that are not aware, these pioneers are responsible for the following
  32. work:
  33.  
  34.                   Ward Christensen ___ Xmodem.
  35.                   Tom Jennings _______ Fido, Telink.
  36.                   Chuck Forsberg _____ Ymodem, Ymodem Batch, Zmodem.
  37.                   Peter Boswell ______ WXmodem.
  38.  
  39. Why Another Protocol?
  40. ---------------------
  41. In many respects, the design of a protocol has become a discussion between
  42. the above mentioned pioneers, each building on the work of the other.  Each
  43. has perceived a weakness in the protocols that have gone before and sought
  44. to improve the art.  And that is the most elegant reason for a new protocol,
  45. to advance the art.
  46.  
  47. I won't bother with a discussion of the merits of Xmodem.  Others have done
  48. that far better than I could.  Let me address the more modern variations.
  49. These are my opinions, based on experience and reading the literature.
  50.  
  51.    Zmodem  - The ideal protocol.  Highly reliable and fast.  Only failing
  52.              is that the cost of implementation is high.
  53.  
  54.    Ymodem  - Very fast, but not network friendly.  Also leaves something
  55.              to be desired on the reliability front.  Error correction is
  56.              slow.
  57.  
  58.    WXmodem - Fast and network friendly.  However, several questions exist
  59.              with regard to reliability.
  60.  
  61. So, it our goal to design and implement a protocol that meets or exceeds
  62. the following criteria:
  63.  
  64.    1.  Fast.  Efficency must exceed 95% on average basis.
  65.    2.  Reliable.  Known defects in prior protocols must be corrected.
  66.    3.  Inexpensive.  Implementation cost must be low.
  67.  
  68.  
  69. How Do We Do It?
  70. ----------------
  71. Let us address these issues in reverse sequence.
  72.  
  73.     COST OF IMPLEMENTATION
  74.     ----------------------
  75.     By closely modeling the protocol after Xmodem, we hope to reduce cost
  76.     of implementation.  This may be a vain effort, because implementation
  77.     of any high performance protocol requires a certain degree of complexity.
  78.  
  79.     RELIABILITY
  80.     -----------
  81.     To improve the reliability of the protocol, we have choosen to use the
  82.     new CRC-32 technology.  The algorithm for this procedure will be given
  83.     later in this document.  Also, the Ack/Nak packets will be composed of
  84.     3 bytes, as was done in the SEAlink protocol.  Like WXmodem we will
  85.     honor all network XOFF signals at the transmitter end.
  86.  
  87.     SPEED
  88.     -----
  89.     Several things are going to be done to improve speed.  First, the block
  90.     size will be increased from 128 to 512 bytes.  This reduces the number
  91.     of envelope characters.  Like Zmodem, MEGAlink will be a full streaming
  92.     protocol, thus eliminating the turn-around time involved with Xmodem
  93.     and Ymodem.
  94.  
  95.  
  96. Some definitions
  97. ----------------
  98.  
  99.      Description             Character           Decimal     Control Char
  100.      -----------             ---------           -------     ------------
  101.      XON ................... DC1 ............... 17 ............ ^Q
  102.      XOFF .................. DC3 ............... 19 ............ ^S
  103.      Acknowledge ........... ACK ............... 6 ............. ^F
  104.      Negative Acknowledge .. NAK ............... 21 ............ ^U
  105.      End of File ........... EOT ............... 4 ............. ^D
  106.      Start of Header ....... SOH ............... 1 ............. ^A
  107.      MegaLink Block Id ..... EM ................ 25 ............ ^Y
  108.      Request Status ........ RS ................ 30 ............ ^^
  109.      Cancel ................ CAN ............... 24 ............ ^X
  110.      Synchronize ........... SYN ............... 22 ............ ^V
  111.      Data Link Escape ...... DLE ............... 16 ............ ^P
  112.      CP/M EOF .............. SUB ............... 26 ............ ^Z
  113.  
  114.  
  115. Receiver discipline
  116. -------------------
  117. The receive side of a MEGAlink transfer has three possible packets it can
  118. use.  Each is three characters in length as follows:
  119.  
  120.       Byte No.          Content
  121.       --------          -------
  122.          1              Ack/Nak/'C'.  No other character may appear.
  123.          2              Packet number.  0 thru 255.
  124.          3              Complement of packet number, i.e. (Pkt# XOR 255).
  125.  
  126. The 'C' packet is sent only at the start of each file transfer.  It is sent
  127. by the receiver at 5 second intervals, until the transmitter begins.  After
  128. that it is not used again until the next file is begun, or the next session
  129. is begun, if only 1 file is transmitted.
  130.  
  131. The Nak packet is used to request the retransmission of the specified packet.
  132.  
  133. The Ack packet is used to indicate the highest packet received without error.
  134.  
  135. Normally, the receiver remains quiet.  The only time packets are required of
  136. the receiver are at the beginning of the transfer, as outlined below, and upon
  137. receipt of an RS character, the Request Status character.  The receiver must
  138. respond to the RS character with an Ack packet, reflecting the highest block
  139. received in without error.  Of course, the receiver should send a Nak packet
  140. whenever a block is received with an error condition.
  141.  
  142. Note, that to maintain network friendliness, no packet may contain a XON or
  143. XOFF character.  These characters must be sent as two characters, first a
  144. DLE, followed by the folded XON or XOFF.  Characters are folded by XOR'ing
  145. them with decimal 64.  This scheme requires that the DLE character is
  146. escaped and folded in the same manner.
  147.  
  148. Transmitter discipline
  149. ----------------------
  150. The transmitter can do four different things:
  151.  
  152.     1)  Send a header block.  Contains file name and other information
  153.         about the file.
  154.  
  155.     2)  Send a data block.  A data block contains 512 bytes of data.
  156.  
  157.     3)  Send an RS character, forces receiver to Ack the highest packet
  158.         he has received without error.
  159.  
  160.     4)  Send an EOT character, signals end-of-file to the receiver.
  161.  
  162.  
  163. Data blocks are sent without pause.  The transmitter should have enough
  164. buffers to cover the turn-around delay, so that any block the receiver
  165. may Nak will still be available in memory for retransmission.
  166.  
  167. Note, that to maintain network friendliness, no packet may contain a XON or
  168. XOFF character.  These characters must be sent as two characters, first a
  169. DLE, followed by the folded XON or XOFF.  Characters are folded by XOR'ing
  170. them with decimal 64.  This scheme requires that the DLE character is
  171. escaped and folded in the same manner.
  172.  
  173. Typical transmit/receive dialog:
  174. --------------------------------
  175.  
  176. Transmitter                           Receiver     Description
  177. -----------                           --------     -----------
  178.                                       C   00 FF    opening Nak.
  179.  
  180. SOH 00 FF  header[128]  CRC CRC                    header block sent,
  181.                                                    using CRC-16.
  182.  
  183.                                       ACK 00 FF    Ack of header block.
  184.  
  185. EM  01 FE  data[512]  CRC CRC CRC CRC              file transmitted in one
  186. EM  02 FD  data[512]  CRC CRC CRC CRC              or more data blocks,
  187. EM  03 FC  data[512]  CRC CRC CRC CRC              using CRC-32.
  188. EM  04 FB  data[512]  CRC CRC CRC CRC
  189.  
  190. RS                                                 transmit requests status.
  191.  
  192.                                       ACK 04 FB    receive replies to RS.
  193.  
  194. EOT                                                end-of-file sent.
  195.  
  196.                                       ACK 04 FB    Ack sent for end-of-file.
  197.  
  198.                                       C   00 FF    opening Nak.
  199.  
  200. EOT                                                end-of-batch sent.
  201.  
  202.                                       ACK 04 FB    Ack sent for end-of-batch.
  203.  
  204. If necessary, the last data block can be padded with CP/M EOF characters.
  205.  
  206. Note: all CRC bytes are transmitted from high to low order, NOT in the
  207.       more usual byte-reversed format.
  208.  
  209. At the end of the transaction, the "opening Nak" is repeated by the receiver.
  210. This is to allow for batch transmission, if more than one file were to be sent
  211. the transmitter would pick-up and start by sending the next header block and
  212. the transaction would continue from that point as shown.
  213.  
  214. The format of the header block conforms to the standard "link" format.
  215. Established by Tom Jennings when he designed the Telink protocol, also
  216. used by the SEAlink protocol.
  217.  
  218.      Byte Offset     Length       Content
  219.      -----------     ------       -------
  220.           0             4         Original file length. Integer in byte
  221.                                   reversed format.
  222.  
  223.           4             4         Date and time file was last mofified, in
  224.                                   seconds since 1979.  Same format DOS uses
  225.                                   in the directory entry.
  226.  
  227.           8            16         Original file name, as a null terminated
  228.                                   string.
  229.  
  230.          24             1         Binary version number.
  231.                                       0 ... Original MegaLink.
  232.                                       1 ... Forsberg's CRC Variation.
  233.  
  234.          25            15         Name of transmitting program, as a null
  235.                                   terminated string.
  236.  
  237.          40            88         Null filler and expansion area.
  238.  
  239. CRC Calculator
  240. --------------
  241. The following routines demonstrate the technique used to calculate CRC's,
  242. both 16 & 32 bit varieties, used in MEGAlink.  The code is written in
  243. Turbo PASCAL.
  244.  
  245. Thanks to Mr. Chuck Forsberg, "Forsberg's CRC Variation" can be introduced.
  246. It involves initializing the CRC Register to $FFFFFFFF instead of the normal
  247. zero.  The use of this variation is signaled by a handshake between transmitter
  248. and receiver.  The receiver sends an opening nak packet containing a 'C' and 2
  249. bytes of 00 and FF hex.  If the receiver desires to use  "Forsberg's CRC
  250. Variation", he should code the bytes following the 'C' as 01 and FE.  If the
  251. transmitter is capable of using "Forsberg's CRC Variation" he will signal this
  252. in the header block, see offset 24 above.  The transmitter will adjust to use
  253. whichever CRC is requested by receiver, thus maintaining downward compatibility.
  254.  
  255.    {  Global Variables  }
  256.  
  257.    TYPE
  258.       ARRAY512       = RECORD
  259.                           Len        : INTEGER;
  260.                           LongString : ARRAY[1..512] OF CHAR;
  261.                        END;
  262.       STRING128      = STRING[128];
  263.    VAR
  264.       crc_input        : INTEGER;      { 2 byte integer format }
  265.       crc_reg_lo       : INTEGER;
  266.       crc_reg_hi       : INTEGER;
  267.       forsberg_variant : BOOLEAN;
  268.  
  269.    PROCEDURE
  270.       ccitt_crc16_calc;                {  CRC-16  }
  271.    BEGIN
  272.       inline( $8B/$1E/crc_reg_hi );    {        mov     bx,crc_reg_hi    }
  273.       inline( $B9/>$08 );              {        mov     cx,8             }
  274.       inline( $A1/crc_input );         {        mov     ax,crc_input     }
  275.       inline( $D0/$D0 );               {  u1:   rcl     al,1             }
  276.       inline( $D1/$D3 );               {        rcl     bx,1             }
  277.       inline( $73/$04 );               {        jnc     u2               }
  278.       inline( $81/$F3/$1021 );         {        xor     bx,1021h         }
  279.       inline( $E2/$F4 );               {  u2:   loop    u1               }
  280.       inline( $89/$1E/crc_reg_hi );    {        mov     crc_reg_hi,bx    }
  281.    END;
  282.  
  283.    PROCEDURE
  284.       ccitt_crc32_calc;                {  CRC-32  }
  285.    BEGIN
  286.       inline( $8B/$1E/crc_reg_lo );    {       mov     bx,crc_reg_lo     }
  287.       inline( $8B/$16/crc_reg_hi );    {       mov     dx,crc_reg_hi     }
  288.       inline( $B9/>$08 );              {       mov     cx,8              }
  289.       inline( $A1/crc_input );         {       mov     ax,crc_input      }
  290.       inline( $D0/$D8 );               {  u1:  rcr     al,1              }
  291.       inline( $D1/$DA );               {       rcr     dx,1              }
  292.       inline( $D1/$DB );               {       rcr     bx,1              }
  293.       inline( $73/$08 );               {       jnc     u2                }
  294.       inline( $81/$F3/$8320 );         {       xor     bx,8320h          }
  295.       inline( $81/$F2/$EDB8 );         {       xor     dx,EDB8h          }
  296.       inline( $E2/$EE );               {  u2:  loop    u1                }
  297.       inline( $89/$1E/crc_reg_lo );    {       mov     crc_reg_lo,bx     }
  298.       inline( $89/$16/crc_reg_hi );    {       mov     crc_reg_hi,dx     }
  299.    END;
  300.  
  301.    PROCEDURE
  302.       calc_crc32(VAR cs : ARRAY512);
  303.    VAR
  304.       i  : INTEGER;
  305.    BEGIN
  306.    (*
  307.         Note: this routine calculates a 32 bit CRC based on the CCITT
  308.               polynomial.  The result is stored in the crc register,
  309.               variables crc_reg_hi & crc_reg_lo.
  310.    *)
  311.       IF (forsberg_variant) THEN BEGIN
  312.          crc_reg_hi:=$FFFF;
  313.          crc_reg_lo:=$FFFF;
  314.       END
  315.       ELSE BEGIN
  316.          crc_reg_hi:=0;
  317.          crc_reg_lo:=0;
  318.       END;
  319.       WITH cs DO BEGIN
  320.          FOR i:=1 TO Len DO BEGIN
  321.             crc_input:=ORD(LongString[i]);
  322.             ccitt_crc32_calc;
  323.          END;
  324.       END;
  325.       crc_input:=0;
  326.       ccitt_crc32_calc;
  327.       ccitt_crc32_calc;
  328.       ccitt_crc32_calc;
  329.       ccitt_crc32_calc;
  330.    END;
  331.  
  332.    PROCEDURE
  333.       calc_crc16(VAR cs : STRING128);
  334.    VAR
  335.       i  : INTEGER;
  336.    BEGIN
  337.    (*
  338.         Note: this routine calculates a 16 bit CRC based on the CCITT
  339.               polynomial.  The result is stored in the crc register,
  340.               variable crc_reg_hi.
  341.    *)
  342.       crc_reg_hi:=0;
  343.       crc_reg_lo:=0;
  344.       FOR i:=1 TO Length(cs) DO BEGIN
  345.          crc_input:=ORD(cs[i]);
  346.          ccitt_crc16_calc;
  347.       END;
  348.       crc_input:=0;
  349.       ccitt_crc16_calc;
  350.       ccitt_crc16_calc;
  351.    END;
  352.  
  353.  
  354. Buffer Management
  355. -----------------
  356. It is the responsibility of the transmitter to have enough buffer space
  357. to cover the Nak turn-around time at a particular baud rate.  Otherwise,
  358. in full stream mode, the receiver may Nak for a block that is not available.
  359. For example, at 2400 baud, assuming a turn-around delay of 6 seconds, the
  360. transmitter should have at least room for 4 blocks in his buffer area.  This
  361. in my opinion, would be cutting it TOO CLOSE, I would recommend a margin of
  362. at least 2 times or more.  In GT PowerComm, the first program to implement
  363. MEGAlink, we have a ring buffer of 32 blocks.  This is very easy to use,
  364. because the the Nak'ed block numbers can be AND'ed with $1F to produce the
  365. buffer number.  At 2400 baud, 32 blocks in the buffer amounts to more than
  366. 60 seconds.  This gives the receive side ample time to turn-around any Nak.
  367.  
  368. Notice that at higher baud rates, the time margin shrinks.  For example,
  369. at 9600 baud, the time margin for 32 blocks shrinks to about 14 seconds.
  370. This would probably be fine for a direct connect, but would not be good
  371. over a network such as PC Pursuit.  (This is not very important now, PC
  372. Pursuit is barely scratching the surface of 2400 baud at this time, 4/20/87.)
  373. At these higher baud rates, the transmitter must use flow control techniques to
  374. insure that an adequate time margin is maintained.  This can be done by issuing
  375. an RS, Request Status, command to the receive side.  The receiver should reply
  376. with an Ack packet indicating the last good packet received.  The transmitter
  377. should wait for reception of this Ack prior to continuing the dialog.  In
  378. effect this is a self-imposed flow control.  The transmitter must be smart
  379. enough to recognize the need for such, based on the baud rate and available
  380. buffer space.  Theoretically, if enough buffer space was available to the
  381. transmitter, it could continue to stream at any baud rate.
  382.  
  383. Error Corrections Procedure
  384. ---------------------------
  385. When the receiver detects an error, it must immediately send a Nak packet
  386. with the offending packet # within.  Then the receiver dumps the contents
  387. of the serial port input buffer and waits for the requested packet.  The
  388. transmitter will not usually be able to respond immediately, so the receiver
  389. must expect packets with higher than expected packet #'s, until the requested
  390. packet arrives.  These extra packets should be disgarded without comment by
  391. receiver.
  392.  
  393. The transmitter, upon receipt of a Nak, will immediately dump the contents of
  394. the serial port output buffer and resend the requested packet.  At this point,
  395. due to the probability of a loss-of-sync error, which cannot be recovered, the
  396. send and receive side now drop to start-stop mode to correct the error.  In
  397. other words, the receiver must Ack a packet that he receives in good shape
  398. after a prior Nak has been sent for the packet.  The sender will not restart
  399. the stream of packets until this Ack has been received.  This prevents any
  400. chance for loss-of-sync at this juncture.  Also important to recognize is
  401. that the receive side of the transfer must have good code to find the start
  402. of a packet.  It will have a fairly unique signature, i.e. the character EM
  403. followed by two characters that are the complements of each other.  Especially
  404. considering the fact that the receiver is looking for a particular packet at
  405. this point, the occurence of a false signature is unlikely.
  406.  
  407. The question of how to handle packets arriving from the receiver that are them-
  408. selves in error has not been addressed.  It is true however, that the trans-
  409. mitter will respond to any Nak.  If the transmitter fails to get a good Nak
  410. the receiver will continue to Nak, until the requested block is received.
  411. This procedure works in practice, however there may well be a more elegant
  412. solution.  For example, the transmitter, upon receipt of a faulty Nak, could
  413. simply wait for the receiver to resend the Nak.  Of course, the transmitter
  414. could also send an RS, request status, command to the receiver, which could
  415. be interpreted in a Nakking situation as a "nak" to the "nak".  This should
  416. cause the receiver to resend the Nak.
  417.  
  418. GT implements the "resend-and-see" approach, this is the most direct and
  419. usually the best.  Even if the Nak is faulty, GT will choose from the 32
  420. buffers and send a block.  If the block is too high or too low, the receiver
  421. will Nak again.  This type of dialog usually leads to a resolution of the
  422. error condition, on all but the worst lines.  Naturally, even the best
  423. protocols fail on the worst lines!
  424.